package cn.dglydrpy.study.algorithm.od;

import java.util.*;

/**
 * @author Yyy
 * @date 2024/11/7 18:57
 * @description
 * 手机 App 防沉迷系统，可注册每个 App 的允许使用时间，一个时段只能使用一个 App，App 有优先级，
 * 高优先级 App 注册时段与低优先级冲突时，系统会自动注销低优先级时段。
 * 根据输入数据注册 App，并根据输入时间点返回可用 App 名称，若该时间点无注册 App 则返回 “NA”。
 *
 * 输入：
3
App1 1 09:00 10:00
App2 3 10:00 11:30
App3 2 09:30 10:30
10:00
 */
public class Od0021_APP {
    public static void main(String[] args) {

//        int n = 2;
//        List<APP> appList = new ArrayList<>();
//        appList.add(new APP("App1",1,"09:00","10:00"));
//        appList.add(new APP("App2",2,"09:10","09:30"));
//        String curTime = "09:50";

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            int n = Integer.valueOf(scanner.nextLine());
            List<APP> appList = new ArrayList<>();
            for(int i=0 ;i<n;i++){
                String[] s = scanner.nextLine().split(" ");
                APP app = new APP(s[0],Integer.valueOf(s[1]),s[2],s[3]);
                appList.add(app);
            }
            String curTime = scanner.nextLine();
            
            String ans = myAnswer(appList,curTime);
            System.out.println(ans);
        }
        

        
    }

    private static String myAnswer(List<APP> appList, String curTime) {
        
        if(appList == null || appList.isEmpty()){
            return "NA";
        }
        
        Collections.sort(appList,(o1,o2)->o2.priority- o1.priority);
//        appList.stream().forEach((o) -> System.out.println(o.appName));

        List<APP> validApps = new ArrayList<>();
        
        for(APP app : appList){
            if(validApps != null){
                boolean canReg = true;
                for(APP validApp : validApps){
                    if(isOverlap(app.startTime,app.endTime,validApp.startTime,validApp.endTime)){
                        canReg = false;
                        break;
                    }
                }
                
                if(canReg){
                    validApps.add(app);
                }
            }else{
                validApps.add(app);
            }
            
        }

        if(validApps == null || validApps.isEmpty()){
            return "NA";
        }
//        System.out.println("validApps: ");
//        validApps.stream().forEach((o) -> System.out.println(o.appName));


        for(APP validApp : validApps){
            if(curTime.compareTo(validApp.startTime) >= 0 && curTime.compareTo(validApp.endTime)<0){
                return validApp.appName;
            }
        }
        return "NA";
        
    }

    public static boolean isOverlap(String start1, String end1, String start2, String end2) {
        // 如果区间 1 的结束位置小于区间 2 的开始位置，或者区间 2 的结束位置小于区间 1 的开始位置，则不重叠
        return!(end1.compareTo(start2)<=0 || end2.compareTo(start1)<=0);
    }

    private static class APP{
        private String appName;
        private int priority;
        private String startTime;
        private String endTime;

        public APP(String appName, int priority, String startTime, String endTime) {
            this.appName = appName;
            this.priority = priority;
            this.startTime = startTime;
            this.endTime = endTime;
        }
    }
}
